package 力扣.堆.滑动窗口.滑动窗口最大值239;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class 滑动窗口最大值239 {
    public static void main(String[] args) {
        int[] ints = {1, 3, -1, -3, 5, 3, 6, 7};
//        int[] ints = {1,-1};
//        int[] ints = {9,11};
//        int[] ints = {4,-2};
//        int[] ints = {4};
//        int[] ints = {0};

        int[] re= maxSlidingWindow2(ints, 3);
        System.out.println(Arrays.toString(re));

    }

    /**
     * 超时版（垃圾）  时间复杂度为 O(kn)
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int max=0;
        ArrayList<Integer> res = new ArrayList<>();
        int count1=len-k+1;

        for (int i = 0; i <count1 ; i++) {
            int count2=i+k;
            max=nums[i];
            for (int j = i+1; j <count2 ; j++) {
                //找到里面的最大值，并添加到res中  但是这里的计算：时间复杂度为 k
                if (nums[j]>max){
                    max=nums[j];
                }
            }
            if (count2 == i){
                max=nums[i];
            }
            res.add(max);
        }
        int[] ints = new int[res.size()];
        for (int i = 0; i < ints.length ; i++) {
            ints[i]=res.get(i);
        }
        //将集合转为包装类的数组，却不能转为基本数据类型的数组
        Integer[] integers = res.toArray(new Integer[(res.size())]);
        return ints;

    }

    /**
     * 我们可以想到，对于两个相邻（只差了一个位置）的滑动窗口.
     * 它们共用着 k-1个元素，而只有 1 个元素是变化的。我们可以根据这个特点进行优化。
     *
     * 使用优先队列
     *
     * 对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {//构造大根堆
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];//比较方式
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});//存储二元组（num[i],index）分别代表数组元素及其下标
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {//当返回队首元素不在窗口里面时移除元素
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];//给每一个窗口的最大值复制给新的数组
        }
        return ans;
    }
}
